package 二叉树;

//import org.w3c.dom.Node;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.Objects;

public class PrintBinaryTree {

    //遍历二叉树
    static public void travelTree(TreeNode root){
        if(root==null){
            System.out.println("null");
            return;
        }

        System.out.println(root.val);
        travelTree(root.left);
        travelTree(root.right);
    }
//    public static class TreeNode {
//        public int val;
//        public TreeNode left;
//        public TreeNode right;
//
//        public TreeNode(int data) {
//            val = data;
//        }
//    }

    public static void printTree(TreeNode head) {
        System.out.println("Binary Tree:");
        printInOrder(head, 0, "H", 17);
        System.out.println();
    }

    public static void printInOrder(TreeNode head, int height, String to, int len) {
        if (head == null) {
            return;
        }
        printInOrder(head.right, height + 1, "v", len);
        String val = to + head.val + to;
        int lenM = val.length();
        int lenL = (len - lenM) / 2;
        int lenR = len - lenL - lenM;
        val = getSpace(lenL) + val + getSpace(lenR);
        System.out.println(getSpace(height * len) + val);
        printInOrder(head.left, height + 1, "^", len);
    }

    public static String getSpace(int num) {
        String space = " ";
        StringBuffer buf = new StringBuffer("");
        for (int i = 0; i < num; i++) {
            buf.append(space);
        }
        return buf.toString();
    }



    // 左右节点分支, 分隔字符, 叶子节点基础间隔
    private static final String TREE_LEFT_BRANCH = "/";
    private static final String TREE_RIGHT_BRANCH = "\\";
    private static final String TREE_SPLIT = " ";
    private static final int TREE_BASE_INTERVAL = 3;

    /**
     * 二叉树打印;
     *
     * @param head 树根节点
     */
    static public void treePrint(TreeNode head) {
        List<List<TreeNode>> allNodes = new ArrayList<>();
        List<TreeNode> curLvNodes = Collections.singletonList(head);
        allNodes.add(curLvNodes);
        while (true) {
            List<TreeNode> list = new ArrayList<>();
            for (TreeNode node : curLvNodes) {
                if (node == null) {
                    list.add(null);
                    list.add(null);
                } else {
                    list.add(node.left);
                    list.add(node.right);
                }
            }
            if (list.stream().allMatch(Objects::isNull)) {
                break;
            }
            curLvNodes = list;
            allNodes.add(curLvNodes);
        }
        StringBuilder sb = new StringBuilder();
        int allLevel = allNodes.size();
        for (int i = 0; i < allNodes.size(); i++) {
            List<TreeNode> nodes = allNodes.get(i);
            Object[] lvValue = new Object[nodes.size()];
            for (int i1 = 0; i1 < nodes.size(); i1++) {
                TreeNode node = nodes.get(i1);
                if (node == null) {
                    lvValue[i1] = TREE_SPLIT;
                } else {
                    lvValue[i1] = "" + node.val;
                }
            }
            String levelString = getLevelString(lvValue, i, allLevel);
            sb.append(levelString).append("\n");
        }
        System.out.printf("tree print:\n{}", sb);
    }

    /**
     * 返回该层打印字符串;
     *
     * @param levelArray 该层的数组
     * @param level 该层层号
     * @param totalLevel 总高度
     * @return 该层打印字符串
     */
    static public String getLevelString(Object[] levelArray, int level, int totalLevel) {
        int levelInterval = (int) Math.pow(2, totalLevel - level + 1) - 1;
        int leftBlank = (levelInterval - TREE_BASE_INTERVAL) / 2;
        String levelIntervalStr = TREE_SPLIT.repeat(levelInterval);

        StringBuilder sb = new StringBuilder();
        if (level > 0) {
            if (leftBlank > 0) {
                sb.append(TREE_SPLIT.repeat(leftBlank));
            }
            for (int i = 0; i < levelArray.length; i++) {
                if (TREE_SPLIT.equals(levelArray[i])) {
                    sb.append(TREE_SPLIT);
                } else {
                    if (i % 2 == 0) {
                        sb.append(TREE_LEFT_BRANCH);
                    } else {
                        sb.append(TREE_RIGHT_BRANCH);
                    }
                }
                if (i < levelArray.length - 1) {
                    sb.append(levelIntervalStr);
                }
            }
            sb.append("\n");
        }
        sb.append(TREE_SPLIT.repeat(leftBlank));
        for (int i = levelArray.length; i > 0; i--) {
            sb.append(levelArray[levelArray.length - i].toString());
            if (i > 1) {
                sb.append(levelIntervalStr);
            }
        }
        return sb.toString();
    }


}
